// 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

// 暴露接口
var combine = function (n: number, k: number): number[][] {
    const res: number[][] = []; // 结果数组
    const path = []; // 当前路径数组
    const isSelected: boolean[] = new Array(n).fill(false); // 是否能被选择，需要减一
    let round: number = 0;// 当前选择轮次
    // 循环结合深度优先遍历找到组合
    for (let i = 0; i < n; i++) {
        isSelected[i] = true;
        path.push(i + 1);
        combine_DFS(n, k, res, path, isSelected, ++round);
        // 回溯部分
        path.pop();
        isSelected[i] = false;
    }
    return res;
};

// 辅助深度优先遍历方法
function combine_DFS(n: number, k: number, res: number[][],
    path: number[], isSelected: boolean[], round: number) {
    // 递归出口，当前路径长度满足k
    if (k === path.length) {
        res.push(Array.from(path)); // 浅拷贝一份结果返回
        return;
    }
    // 深度优先搜索
    for (let i = round - 1; i < n; i++) {
        if (!isSelected[i]) {
            isSelected[i] = true;
            path.push(i + 1);
            combine_DFS(n, k, res, path, isSelected, ++round);
            // 回溯算法部分
            isSelected[i] = false;
            path.pop();
        }
    }
}


// 这道题目也是一道经典的可以用模板套路解决的问题
// 主要使用的方法是深度优先遍历结合回溯算法，
// 要注意的是这里的深度优先搜索要限定在一个循环的框架之下
// 找组合排列的过程就让深度优先遍历和回溯来完成，
// 我们需要一个结果数组、一个权限数组（表示是否能被选择）、当前的路径数组，
// 其中回溯算法保证了当前路径的状态重置部分，不然选择后的路径无法撤回到原状态
// 但在本题中需要注意警惕重复的部分：有的选择会产生重复的组合-->例如[1,2]和[2,1]
// 重复的选择应该要被剪枝剪掉，那怎么剪掉这个部分？
// 先确定一个变量作为当前的轮次
// 我们在DFS中选择的时候，开始选择的坐标应该是上一次选择的坐标+1
// 即新选择的元素只往右侧考虑，而不选左侧的，这样就防止了结果中出现的重复
// 额外注意一下在回溯算法的过程中，因为传入的round是值拷贝而不是引用，所以是不需要做状态回溯的。